package com.study.lu;

public class 放硬币 {

    /**
     * 给定一些硬币，第一行放一枚，第二行放两枚。。。 第n行放n枚，
     * 求最多能放几行  eg 给10枚，能放 1+2+3+4 =10 即四行
     *
     * @param args
     */
    public static void main(String[] args) {
        System.out.println(bf(16));

        System.out.println(bf2fenchazhao(16));

        System.out.println((int) newTon(16));

    }

    /**
     * 根据二分查找公式可得
     * （1+2+3....+n） = x
     * (1+n)n/2=x
     * n+n^2=2x
     * n^2 =2x-n
     * 把 n^2 看成 XX
     * 把 2x-n 看成 根号N
     * 即 XX = 根号N*根号N
     * 所以可以参考牛顿迭代 代码实现参考SqartTest
     * 牛顿迭代平方根的公式为
     *  x == n^2
     *  n == (n+x/n)/2  而这里的n == (2x-n)
     *
     * @param total
     * @return
     */
    private static double newTon(int total) {

        if (total == 0) {
            return total;
        }

        return sqart(total, total);

    }

    private static double sqart(double n, int x) {

        double res = (n + (2 * x - n) / n) / 2;
        if (res == n) {
            return res;
        } else {
            return sqart(res, x);
        }
    }

    /**
     * 二分查找：假设n为第n行 x为总硬币数  那么总共从第一行的硬币数+到第n行的硬币数之和等于x。那么就知道能放多少行（n行）
     *
     * @param total
     * @return
     */
    private static int bf2fenchazhao(int total) {

        int low = 0, height = total;

        while (low <= height) {
            int mid = (height + low) / 2;
            double i = (1 + mid) * mid / 2;
            if (i == total) {
                return mid;
            } else if (i > total) {
                height = mid - 1;
            } else {
                low = mid + 1;
            }

        }

        // 这里为啥要返回height 是要返回最小值，因为最大值不够，最小值有多。。
        return height;

    }

    /**
     * 暴力算法：
     * 从第一行开始往上相加 直到剩余的硬币数小于等于第n行位置
     *
     * @param total
     * @return
     */
    private static int bf(int total) {
        int sum = 0;
        for (int i = 0; i < total; i++) {
            sum = sum + i;
            if (total - sum <= i) {
                return i;
            }
        }

        return -1;
    }
}
